// 参考链接：https://www.cnblogs.com/maburb/p/18981181
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5 + 10;
vector<pair<int, int>> adj[MN]; // 邻接表存储图，pair<相邻节点, 边编号>

int cnt[21][MN];        
// cnt[i][u]: 到节点u时距离模k为i的次数

int st[21][2 * MN - 1]; 
// st[t][id]: 边id在模k为t的状态下是否访问过

int ans[MN];            
// 存储每个节点的最终答案

void solve() {
  int n, k;
  cin >> n >> k;
  // 构建图的邻接表
  for (int i = 0; i + 1 < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v; // 转换为0-based索引
    // 为每条无向边分配两个有向边编号
    adj[u].emplace_back(v, i * 2);
    adj[v].emplace_back(u, i * 2 + 1);
    // (0,1) (2,3)  同一条边的正向边 ^1 = 反向边编号  2^1=3 ,  3^1=2
  }

  const int inf = 1e9;
  memset(ans, -1, sizeof(ans)); // 初始化答案为-1

  queue<tuple<int, int, int>> q; // BFS队列：(当前步数, 当前节点, 上一条边编号)
  q.emplace(0, 0, -1);           // 从节点0开始，初始步数为0，无上一条边
  while (q.size()) {
    int u, d, fa;
    tie(d, u, fa) = q.front();
    q.pop();

    // 当步数是k的倍数时更新答案
    if (d % k == 0 && ans[u] == -1) {
      ans[u] = d / k;
    }

    // 同一状态访问超过两次则跳过
    if (++cnt[d % k][u] > 2) {
      continue;
    }

    // 遍历相邻节点
    for (auto &son : adj[u]) {
      int v, id;
      tie(v, id) = son;  // u->v ,  id 为 u->v 的边编号

      // 避免立即走回头路（除非步数是k的倍数）
      //  若 u->v 为正向边， 则 u->v^1 为反向边v->u
      // (u->v) ^ (v->u) = 1
      if ((fa ^ id) == 1 && d % k != 0) {
        continue;
      }

      // 如果该边在当前模数状态下未访问过
      if (!st[(d + 1) % k][id]) {
        st[(d + 1) % k][id] = 1;
        q.emplace(d + 1, v, id);
      }
    }
  }

  // 输出结果
  for (int i = 1; i < n; ++i) {
    cout << ans[i] << " \n"[i == n - 1];
  }
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
